//
// class dsVECTOR implementation
//

/***************************************************************
* dsVECTOR::dsVECTOR ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE dsVECTOR<T,ALIGNMENT>::dsVECTOR(/*apCL cl*/) : pData(NULL), nElem(0), allocated(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(cl)
//#endif
{
   return ;
}
/***************************************************************
* dsVECTOR::dsVECTOR ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE dsVECTOR<T,ALIGNMENT>::dsVECTOR(int size/*, apCL cl*/) : pData(NULL), nElem(0), allocated(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(cl)
//#endif
{
   Resize(size);
   return ;
}

/***************************************************************
* dsVECTOR::dsVECTOR ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE dsVECTOR<T,ALIGNMENT>::dsVECTOR(int size, const T &val/*, apCL cl*/) : pData(NULL), nElem(0), allocated(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(cl)
//#endif
{
   Resize(size, val);
   return ;
}

/***************************************************************
* dsVECTOR::dsVECTOR ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE dsVECTOR<T,ALIGNMENT>::dsVECTOR(const dsVECTOR &src/*, apCL cl*/) : pData(NULL), nElem(0), allocated(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(src.__cl)
//#endif
{
   Insert(0, src.pData, src.nElem);
   return ;
}

/***************************************************************
* dsVECTOR::dsVECTOR ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE dsVECTOR<T,ALIGNMENT>::dsVECTOR(const T *begin, int num/*, apCL cl*/) : pData(NULL), nElem(0), allocated(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(cl)
//#endif
{
   Insert(0, begin, num);
   return ;
}

/***************************************************************
* dsVECTOR::~dsVECTOR ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE dsVECTOR<T,ALIGNMENT>::~dsVECTOR(void)
{
   int   i;
   
   for (i = 0; i < nElem; i++) {
      (pData + i)->~T();
   }

   _internalFree(pData);

#ifdef _DEBUG
   pData = NULL;
   nElem = 0;
   allocated = 0;
#endif

   return ;
}

/***************************************************************
* dsVECTOR::operator = ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE const dsVECTOR<T,ALIGNMENT>& dsVECTOR<T,ALIGNMENT>::operator =(const dsVECTOR &src)
{
   if (src.pData == pData) {
      return *this;
   }
   
   Clear();
   if (allocated != src.nElem) {
      Compact();
   }
   Insert(0, src.pData, src.nElem);
   return *this;
}

/***************************************************************
* dsVECTOR::Swap ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Swap(dsVECTOR<T,ALIGNMENT> &arr)
{
   T  *tmp;
   int t;

   tmp = pData; pData = arr.pData; arr.pData = tmp;
   t = nElem; nElem = arr.nElem; arr.nElem = t;
   t = allocated; allocated = arr.allocated;  arr.allocated = t;

   return;
}

/***************************************************************
* dsVECTOR::internalRealloc ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Realloc(int size)
{
   ASSERT(size >= 0);

   if (size == allocated) {
      return;
   }
   ShrinkResize(size);
   STRONG_ASSERT2(size >= nElem, size, nElem);

   _internalRealloc(size);

   ASSERT(pData || size == 0);

   allocated = size;
   return;
}


/***************************************************************
* dsVECTOR::_internalRealloc ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::_internalRealloc(int size)
{
#ifdef AP_USE_MEM_STAT
   if (ALIGNMENT<=8) {
      pData = (T*)dlRealloc(pData, size * sizeof(T), __cl.file, __cl.line);
   } else {
      pData = (T*)dlReallocAligned(pData, size * sizeof(T), ALIGNMENT, __cl.file, __cl.line);
   }
#else 
   //if (ALIGNMENT<=8) {
   //   pData = (T*)dlRealloc(pData, size * sizeof(T), NULL, 0);
   //} else {
   //   pData = (T*)dlReallocAligned(pData, size * sizeof(T), ALIGNMENT, NULL, 0);
   //}
   pData = (T *)realloc(pData, size * sizeof(T));
#endif
}


/***************************************************************
* dsVECTOR::_internalFree ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::_internalFree(void *p)
{
   free(p);
   //if (ALIGNMENT<=8) {
   //   dlFree(p);
   //} else {
   //   dlFreeAligned(p);
   //}
}

/***************************************************************
* dsVECTOR::Reserve ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Reserve(int size)
{
   if (size > allocated) {
      Realloc(size);
   }
   return ;
}

/***************************************************************
* dsVECTOR::Compact ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Compact(void)
{
   Realloc(nElem);
   return ;
}

/***************************************************************
* dsVECTOR::Resize ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Resize(int size)
{
   STRONG_ASSERT1(size >= 0, size);

   if (size <nElem) {
      for (int i = size; i < nElem; i++) {
         (pData + i)->~T();
      }
   } else if (size > nElem) {
      Reserve(size);
      for (int i = nElem; i < size; i++) {
#ifdef AP_USE_MEM_STAT
         CallNew(pData + i);
#else
         New(pData + i);
#endif
      }
   }
   nElem = size;

   return ;
}

/***************************************************************
* dsVECTOR::Resize ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Resize(int size, const T &val)
{
   STRONG_ASSERT1(size >= 0, size);

   int      i;

   if (size < nElem) {
      for (i = size; i < nElem; i++) {
         (pData + i)->~T();
      }
   } else if (size > nElem) {
      if (size > allocated) {
         T v =  val;
         Reserve(size);
         for (i = nElem; i < size; i++) {
            New(pData + i, v);
         }
      } else {
         for (i = nElem; i < size; i++) {
            New(pData + i, val);
         }
      }
   }
   nElem = size;
     
   return ;
}

/***************************************************************
* dsVECTOR::SrinkResize ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::ShrinkResize(int size)
{
   STRONG_ASSERT1(size >= 0, size);

   if (size < nElem) {
      for (int i = size; i < nElem; i++) {
         (pData + i)->~T();
      }
      nElem = size;
   }
   return;
}

/***************************************************************
* dsVECTOR::GrowResize ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::GrowResize(int size)
{
   if (size > nElem) {
      Resize(size);
   }
   return ;
}

/***************************************************************
* dsVECTOR::GrowResize ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::GrowResize(int size, const T &val)
{
   if (size > nElem) {
      Resize(size, val);
   }
   return ;
}

/***************************************************************
* dsVECTOR::GrowResize_NoNew ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::GrowResize_NoNew (int size)
{
   if (allocated < size) {
      Reserve(max(allocated * 2, size));
   }
   nElem = size;
   return;
}

/***************************************************************
* dsVECTOR::Clear ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Clear(void)
{
   for (int i = 0; i < nElem; i++) {
      (pData + i)->~T();
   }
   nElem = 0;
   return;
}

/***************************************************************
* dsVECTOR::Insert ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Insert(int pos, const T &val, int n)
{
   // it will crash later, so make crash here
   STRONG_ASSERT3(pos >=0 && pos <= nElem && n >= 0, pos, nElem, n);

   if (n == 0) {
      return;
   }

   if (allocated < nElem + n) {
      // local copy is made for case when &val is dsVECTOR's element and Reserve (realloc) will 
      // invalidate the area in memory where it is located, leading to unpredicted behavior
      T v = val;
      Reserve(max(allocated * 2, nElem + n));
#ifdef __GCC__
      volatile int p = pos; // GCC falls to ICE otherwise
      memmove(pData + pos + n, pData + pos, (nElem - p) * sizeof(T));
#else
      memmove(pData + pos + n, pData + pos, (nElem - pos) * sizeof(T));
#endif
      for (int i = pos; i < pos + n; i++) {
         New(pData + i, v);
      }
   } else {
#ifdef __GCC__
      volatile int p = pos; // GCC falls to ICE otherwise
      memmove(pData + pos + n, pData + pos, (nElem - p) * sizeof(T));
#else
      memmove(pData + pos + n, pData + pos, (nElem - pos) * sizeof(T));
#endif
      for (int i = pos; i < pos + n; i++) {
         New(pData + i, val);
      }
   }

   nElem += n;

   return;
}

/***************************************************************
* dsVECTOR::Insert ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Insert(int pos, const T *begin, int num)
{
   // it will crash later, so make crash here
   STRONG_ASSERT3(pos >=0 && pos <= nElem && num >= 0, pos, nElem, num);

   if (num == 0) {
      return;
   }

   T *oldPtr = pData;

   if (allocated < nElem + num) {
      Reserve(max(allocated * 2, nElem + num));
   }

   if (begin >= oldPtr && begin < oldPtr + nElem) {
      begin = begin + (pData - oldPtr);
   }

   memmove(pData + pos + num, pData + pos, (nElem - pos) * sizeof(T));

   for (int i = pos; i < pos + num; i++) {
      New(pData + i, *begin);
      begin++;
   }

   nElem += num;
   
   return;
}

/***************************************************************
* dsVECTOR::Erase ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::Erase(int pos, int n)
{
   // it will crash later, so make crash here
   STRONG_ASSERT3(pos >=0 && n >= 0 && pos + n <= nElem, pos, nElem, n);

   if (n == 0) {
      return ;
   }

   for (int i = pos; i < pos + n; i++) {
      (pData + i)->~T();
   }

   memmove(pData + pos, pData + pos + n, (nElem - pos - n) * sizeof(T));

   nElem -= n;
   
   return;
}

/******************************************************************************
* dsVECTOR<T, ALIGNMENT>::Erase
*
******************************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::EraseNonSorted(int pos)
{
   // it will crash later, so make crash here
   STRONG_ASSERT2(pos >=0 && pos < nElem, pos, nElem);

   // delete current element
   (pData + pos)->~T();

   if (pos + 1 < nElem) {
      // copy last to this position
      memcpy(pData + pos, pData + nElem - 1, sizeof(T));
   }

   --nElem;
}

/***************************************************************
* dsVECTOR::PushBack ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE T& dsVECTOR<T,ALIGNMENT>::PushBack(const T &val)
{
   if (allocated < nElem + 1) {
      // local copy is made for case when &val is dsVECTOR's element and Reserve (realloc) will 
      // invalidate the area in memory where it is located, leading to unpredicted behavior
      T v = val;
      Reserve(max(allocated * 2, nElem + 1));
      New(pData + nElem, v);
   } else {
      New(pData + nElem, val);
   }

   nElem++;

   return Back();
}

/***************************************************************
* dsVECTOR::PopBack ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE void dsVECTOR<T,ALIGNMENT>::PopBack(void)
{
   // safety block
   if (nElem == 0) {
      ASSERT_ALOOF_CODE();
      return;
   }

   // relay
   ShrinkResize(nElem - 1);
}

/***************************************************************
* dsVECTOR::Front ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE const T& dsVECTOR<T,ALIGNMENT>::Front(void) const 
{
   STRONG_ASSERT1(nElem > 0, nElem);
   return pData[0];
}

/***************************************************************
* dsVECTOR::Front ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE T& dsVECTOR<T,ALIGNMENT>::Front(void) 
{
   STRONG_ASSERT1(nElem > 0, nElem);
   return pData[0];
}

/***************************************************************
* dsVECTOR::Back ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE const T& dsVECTOR<T,ALIGNMENT>::Back(void) const 
{
   STRONG_ASSERT1(nElem > 0, nElem);
   return pData[nElem-1];
}

/***************************************************************
* dsVECTOR::Back ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE T& dsVECTOR<T,ALIGNMENT>::Back(void) 
{
   STRONG_ASSERT1(nElem > 0, nElem);
   return pData[nElem-1];
}

/***************************************************************
* dsVECTOR::Back ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE const T& dsVECTOR<T,ALIGNMENT>::Back(int index) const 
{
   STRONG_ASSERT2(nElem > index, index, nElem);
   return pData[nElem - 1 - index];
}

/***************************************************************
* dsVECTOR::Back ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE T& dsVECTOR<T,ALIGNMENT>::Back(int index) 
{
   STRONG_ASSERT1(nElem > index, nElem);
   return pData[nElem - 1 - index];
}

/***************************************************************
* dsVECTOR::operator [] ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE const T& dsVECTOR<T,ALIGNMENT>::operator [](int idx) const
{
   STRONG_ASSERT2(idx >= 0 && idx < nElem, idx, nElem);
   return pData[idx];
}

/***************************************************************
* dsVECTOR::operator [] ()
*
***************************************************************/
template <class T, UINT ALIGNMENT> __INLINE T& dsVECTOR<T,ALIGNMENT>::operator [](int idx)
{
   STRONG_ASSERT2(idx >= 0 && idx < nElem, idx, nElem);
   return pData[idx];
}

/***************************************************************
* dsVECTOR::Sort [] ()
*
***************************************************************/
template <class T, UINT ALIGNMENT>  
   template <class CMP, class SWAP> __INLINE
void dsVECTOR<T,ALIGNMENT>::Sort(const CMP &cmp_, const SWAP &swap)
{
#ifdef _DEBUG
   dsCHECKED_CMP<CMP> cmp(cmp_);
#else
   const CMP & cmp = cmp_;
#endif

   if (Length() > 100) {
      HeapSort(cmp, swap);
      return ;
   }

   for (int i = 0; i < nElem - 1; i++) {
      for (int j = i + 1; j < nElem; j++) {
         if (cmp.cmp(pData[j], pData[i]) < 0) {
            swap(pData[i], pData[j]);
         }
      }
   }
}

template<class T, UINT ALIGNMENT> template <class CMP, class SWAP>
inline void dsVECTOR<T,ALIGNMENT>::Sisp(int p, int q, T * array, const CMP & cmp, const SWAP & swap)
{
   int i = p, j = i*2;
   typename SWAP::TMP_T x(array[i]);
   if (j < q && cmp.cmp(array[j], array[j+1]) < 0) {
      ++j;
   }

   while (j <= q && cmp.cmp(x, array[j]) < 0) {
      swap.copy(array[i], array[j]); i = j; j = j*2;
      if (j < q && cmp.cmp(array[j], array[j+1]) < 0) {
         ++j;
      }
   }
   swap.copy(array[i], x);
}

template<class T, UINT ALIGNMENT> template <class CMP, class SWAP>
inline void dsVECTOR<T,ALIGNMENT>::HeapSort(const CMP & cmp, const SWAP & swap)
{
   T * array = pData - 1;
   int q = Length();
   for (int i = Length(); i > 0; --i) {
      Sisp(i, Length(), array, cmp, swap);
   }

   while (q > 1) {
      swap(array[1], array[q]);
      --q;
      Sisp(1, q, array, cmp, swap);
   }

   // make sure that everything has been sorted successfully
   for (int k=0; k + 1 < Length(); ++k) {
      if (cmp.cmp(pData[k], pData[k+1]) > 0) {
         ASSERT(cmp.cmp(pData[k], pData[k+1]) <= 0);
         // oops...
         for (int i = 0; i < nElem - 1; i++) {
            for (int j = i + 1; j < nElem; j++) {
               if (cmp.cmp(pData[j], pData[i]) < 0) {
                  swap(pData[i], pData[j]);
               }
            }
         }

         return ;
      }
   }
}

/***************************************************************
* dsVECTOR::InvSort ()
*
***************************************************************/
template <class T, UINT ALIGNMENT>
   template <class CMP, class SWAP> __INLINE
void dsVECTOR<T,ALIGNMENT>::InvSort(const CMP &cmp, const SWAP &swap)
{
   Sort(dsCMP_INV<CMP>(cmp), swap);
}

/***************************************************************
* dsVECTOR::InsertSorted ()
*   insert element into the sorted array
***************************************************************/
template <class T, UINT ALIGNMENT>
   template <class CMP> __INLINE
int dsVECTOR<T,ALIGNMENT>::InsertSorted(const T &val, const CMP &cmp, INS_SORT dup/* = INS_DUP_IGNORE*/)
{
   int      rc, begin, end, cur;

   begin = 0; end = nElem;

   for (;;) {
      if (begin == end) {
         // insert element at this pos
         Insert(begin, val);
         return begin;
      }

      cur = (begin + end) >> 1;

      rc = cmp.cmp(pData[cur], val);
      if (rc > 0) { 
         end = cur; // key is less -> look left half
      } else if (rc < 0) { 
         begin = cur + 1; // key is greater -> look right half
      } else {
         switch (dup) {
               case INS_DUP_REPLACE:
                  pData[cur] = val;
                  return cur;
               case INS_DUP_IGNORE:
                  return cur;
               case INS_DUP_RIGHT:
                  Insert(cur, val);
                  return cur;
               default:
                  return -1;
         }
      }
   }
}

/***************************************************************
* dsVECTOR::FindSorted ()
*    search element cmp(elem, key)==0 in sorted array, return -1 if not found
*    array MUST BE SORTED !!!!
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP, class KEY> __INLINE
int dsVECTOR<T,ALIGNMENT>::FindSorted (const KEY &key, const CMP &cmp) const
{
   int      begin, end, cur, rc;

   begin = 0; end = nElem;

   while(1) {
      if (begin == end) {
         break;
      }

      cur = (begin + end) >> 1;

      rc = cmp.cmp(pData[cur], key);
      if (rc > 0) { 
         end = cur; // key is less -> look left half
      } else if (rc < 0) { 
         begin = cur + 1; // key is greater -> look right half
      } else {
         return cur; // key found
      }
   }
   return -1;
}

/***************************************************************
* dsVECTOR::FindSortedFirst ()
* DESCRIPTION:
*    search first element cmp(elem, key)==0 in sorted array, return -1 if not found
*    array MUST BE SORTED !!!!
* TODO:
*	Implement :)
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP, class KEY> __INLINE
int dsVECTOR<T,ALIGNMENT>::FindSortedFirst (const KEY &key, const CMP &cmp) const
{
   //int      begin, end, cur, rc;

   //begin = 0; end = nElem;

   //while(1) {
   //   if (begin == end) {
   //      break;
   //   }

   //   cur = (begin + end) >> 1;

   //   rc = cmp.cmp(pData[cur], key);
   //   if (rc >= 0) { 
   //      end = cur; // key is less -> look left half
   //   } else if (rc < 0) { 
   //      begin = cur + 1; // key is greater -> look right half
   //   }
   //}
   //if (end == nElem) {// all elements are greater than key
   //   return -1;
   //}
   //if (cmp.cmp(pData[end + 1], key);)
   return -1;
}

/***************************************************************
* dsVECTOR::FindSortedFirstGreater ()
* DESCRIPTION:
*    Find first <elem>: cmp(elem, key) == 1  in sorted array
*    array MUST BE SORTED !!!!
* TEST:
*  key = 2
*  | array |  b |  e |  c |
*  | 01234 |    |    |    |
*  ------------------------
*  | 2     |  0 |  0 |  0 |
*  |       |  1 |  0 |    |
*  ------------------------
*  | 3     |  0 |  0 |  0 |
*  |       |  0 | -1 |    |
*  ------------------------
*  | 22    |  0 |  1 |  0 |
*  |       |  1 |  1 |  1 |
*  |       |  2 |  1 |    |
*  ------------------------
*  | 23    |  0 |  1 |  0 |
*  |       |  1 |  1 |  1 |
*  |       |  1 |  0 |    |
*  ------------------------
*  | 33    |  0 |  1 |  0 |
*  |       |  0 | -1 |    |
*  ------------------------
*  | 222   |  0 |  2 |  1 |
*  |       |  2 |  2 |  2 |
*  |       |  3 |  2 |    |
*  ------------------------
*  | 223   |  0 |  2 |  1 |
*  |       |  2 |  2 |  2 |
*  |       |  2 |  1 |    |
*  ------------------------
*  | 233   |  0 |  2 |  1 |
*  |       |  0 |  0 |  0 |
*  |       |  1 |  0 |    |
*  ------------------------
*  | 333   |  0 |  2 |  1 |
*  |       |  0 |  0 |  0 |
*  |       |  0 | -1 |    |
*  (begin contains the answer after all iterations)
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP, class KEY> __INLINE
int dsVECTOR<T,ALIGNMENT>::FindSortedFirstGreater(const KEY &key, const CMP &cmp, int begin, int end) const
{
   STRONG_ASSERT(begin >= 0);
   STRONG_ASSERT(end < nElem);
   int b = begin, e = end;
   while (b <= e) {
      int cur = (b + e) >> 1;
      int rc = cmp.cmp(pData[cur], key);
      if (rc > 0) {// pData[cur] > key -> look left half, because we look for first greater
         e = cur - 1;
      } else {// pData[cur] <= key -> look right half
         b = cur + 1;
      }
   }
   return b;
}


/***************************************************************
* dsVECTOR::FindFirstGESorted ()
*    search first element cmp(elem, key)>=0 in sorted array, return Length() if all less
*    array MUST BE SORTED !!!!
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP, class KEY> __INLINE
int dsVECTOR<T,ALIGNMENT>::FindSortedFirstGE(const KEY &key, const CMP &cmp) const
{
   int      begin, end, cur, rc;

   begin = 0; end = nElem;

   while(1) {
      if (begin == end) {
         break;
      }

      cur = (begin + end) >> 1;

      rc = cmp.cmp(pData[cur], key);
      if (rc > 0) { 
         end = cur; // key is less -> look left half
      } else if (rc < 0) { 
         begin = cur + 1; // key is greater -> look right half
      } else {
         while (cur > 0 && cmp.cmp(pData[cur - 1], key) == 0) {
            cur--;
         }
         return cur; // key found
      }
   }
   return begin;
}

/***************************************************************
* dsVECTOR::FindLowerBound ()
*    Returns an index of the first element in the sorted array which does not compare less than value. 
*    array MUST BE SORTED !!!!
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP, class KEY> __INLINE
int dsVECTOR<T,ALIGNMENT>::FindLowerBound(const KEY &key, const CMP &cmp) const
{
  int len = nElem;
  int first = 0;

  while (len > 0) {
    int half = len >> 1;
    int middle = first + half;
    int rc = cmp.cmp(pData[middle], key);
    if (rc < 0) {
      ASSERT(cmp.cmp(key, pData[middle]) >= 0); // strict weak ordering
      first = middle + 1;
      len -= half + 1;
    }
    else {
      ASSERT(cmp.cmp(key, pData[middle]) <= 0); // strict weak ordering
      len = half;
    }
  }
  return first;
}

/***************************************************************
* dsVECTOR::FindSortedLastLess ()
* DESCRIPTION:
*  Search last element cmp(elem, key)==-1 in sorted array,
*  return -1 if no elements before
*  array MUST BE SORTED !!!!
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP, class KEY> /*__INLINE*/
int dsVECTOR<T,ALIGNMENT>::FindSortedLastLess (const KEY &key, const CMP &cmp) const
{
   int begin = 0, end = nElem;
   int rc = -1;
   while(1) {
      if (begin == end) {
         break;
      }

      int cur = (begin + end) >> 1;

      rc = cmp.cmp(pData[cur], key);
      if (rc >= 0) { 
         end = cur; // key is less-equal -> look left half
      } else { 
         begin = cur + 1; // key is greater -> look right half
      }
   }

   // After cycle "begin" (or "end") points at last less or after last less

   if (end == nElem) {
      // Element is greater then last element
      return nElem - 1;
   }
   rc = cmp.cmp(pData[end], key);
   if (rc < 0) {// end points at last less
      return end;
   } else {
      return end - 1;
   }
}


/***************************************************************
* dsVECTOR::Find [] ()
*    search first element cmp(elem, key)==0 in sorted array, return -1 if not found
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP, class KEY> __INLINE
int dsVECTOR<T,ALIGNMENT>::Find(const KEY &key, const CMP &cmp, int startPos) const
{
   int      begin, end, rc;

   if (startPos >= nElem) {
      return -1;
   }

   begin = startPos; end = nElem;

   while(begin != end) {
      rc = cmp.cmp(pData[begin], key);
      if (rc == 0) {
         return begin;
      }
      begin++;
   }
   return -1;
}

template <class T, UINT ALIGNMENT>  
template <class CMP>
void dsVECTOR<T,ALIGNMENT>::Difference(const dsVECTOR<T,ALIGNMENT> &arr1,const  dsVECTOR<T,ALIGNMENT> &arr2, const CMP &cmp){
   const T *First1 = arr1.Begin();
   const T *First2 = arr2.Begin();

   const T *Last1 = arr1.End();
   const T *Last2 = arr2.End();

   while(First1 < Last1 &&  First2 < Last2){
      int iResult = cmp.cmp(*First1,*First2);

      if(iResult > 0){
         PushBack(*First2);
         ++First2;
      }
      else if (iResult < 0){
         PushBack(*First1);
         ++First1;
      }
      else{
         ++First1;
         ++First2;
      }
   }
   for (;First1 < Last1;First1++)
      PushBack(*First1);
   for (;First2 < Last2;First2++)
      PushBack(*First2);
}


template <class T, UINT ALIGNMENT>  
template <class CMP>
void dsVECTOR<T,ALIGNMENT>::Common(const dsVECTOR<T,ALIGNMENT> &arr1,const  dsVECTOR<T,ALIGNMENT> &arr2, const CMP &cmp){
   const T *First1 = arr1.Begin();
   const T *First2 = arr2.Begin();

   const T *Last1 = arr1.End();
   const T *Last2 = arr2.End();

   while(First1 < Last1 &&  First2 < Last2){
      int iResult = cmp.cmp(*First1,*First2);

      if(iResult > 0){
         ++First2;
      }
      else if (iResult < 0){
         ++First1;
      }
      else{
         PushBack(*First2);
         ++First1;
         ++First2;
      }
   }
}

template <class T, UINT ALIGNMENT>  
T & dsVECTOR<T, ALIGNMENT>::operator += (const T & p) {
   return PushBack(p);
}


//////////////////////////////////////////////////////////////////////////
// dsARRAY
//////////////////////////////////////////////////////////////////////////

/***************************************************************
* dsARRAY::dsARRAY ()
*
***************************************************************/
template <class T> __INLINE dsARRAY<T>::dsARRAY(/*apCL cl*/) : pData(NULL), nElem(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(cl)
//#endif
{
   return ;
}
/***************************************************************
* dsARRAY::dsARRAY ()
*
***************************************************************/
template <class T> __INLINE dsARRAY<T>::dsARRAY(int size/*, apCL cl*/) : pData(NULL), nElem(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(cl)
//#endif
{
   Resize(size);
   return ;
}

/***************************************************************
* dsARRAY::dsARRAY ()
*
***************************************************************/
template <class T> __INLINE dsARRAY<T>::dsARRAY(int size, const T &val/*, apCL cl*/) : pData(NULL), nElem(0)
//#ifdef AP_USE_MEM_STAT
//, __cl(cl)
//#endif
{
   Resize(size, val);
   return ;
}

/***************************************************************
* dsARRAY::dsARRAY ()
*
***************************************************************/
template <class T> __INLINE dsARRAY<T>::dsARRAY(const dsARRAY &src/*, apCL cl*/) : pData(NULL), nElem(0)
#ifdef AP_USE_MEM_STAT
, __cl(src.__cl)
#endif
{
   Resize(src.Length());
   memcpy(Begin(), src.Begin(), src.Length() * sizeof(T));
   return ;
}

/***************************************************************
* dsARRAY::~dsARRAY ()
*
***************************************************************/
template <class T> __INLINE dsARRAY<T>::~dsARRAY(void)
{
   Resize(0);
#ifdef _DEBUG
   pData = (T*)0xFEEFEFFE;
   nElem = 0xABCDABCD;
#endif
   return ;
}

/***************************************************************
* dsARRAY::operator = ()
*
***************************************************************/
template <class T> __INLINE const dsARRAY<T>& dsARRAY<T>::operator =(const dsARRAY &src)
{
   if (src.pData == pData) {
      return *this;
   }
   Resize(0);
   Resize(src.Length());
   memcpy(Begin(), src.Begin(), src.Length() * sizeof(T));
   return *this;
}

/***************************************************************
* dsARRAY::Swap ()
*
***************************************************************/
template <class T> __INLINE void dsARRAY<T>::Swap(dsARRAY<T> &arr)
{
   T  *tmp;
   int t;

   tmp = pData; pData = arr.pData; arr.pData = tmp;
   t = nElem; nElem = arr.nElem; arr.nElem = t;

   return;
}

/***************************************************************
* dsARRAY::Realloc ()
*
***************************************************************/
template <class T> __INLINE void dsARRAY<T>::Realloc(int size)
{
   STRONG_ASSERT1(size >= 0, size);

   if (size == 0) {
      dlFree(pData);
      pData = NULL;
      return;
   }
   
#ifdef AP_USE_MEM_STAT
   pData = (T*)dlRealloc(pData, size * sizeof(T), __cl.file, __cl.line);
#else 
   pData = (T*)dlRealloc(pData, size * sizeof(T), NULL, 0);
#endif

   return;
}

/***************************************************************
* dsARRAY::Resize ()
*
***************************************************************/
template <class T> __INLINE void dsARRAY<T>::Resize(int size)
{
   STRONG_ASSERT1(size >= 0, size);

   if (size < nElem) {
      for (int i = size; i < nElem; i++) {
         (pData + i)->~T();
      }
      Realloc(size);
   } else if (size > nElem) {
      Realloc(size);
      for (int i = nElem; i < size; i++) {
#ifdef AP_USE_MEM_STAT
         CallNew(pData + i);
#else
         New(pData + i);
#endif
      }
   }
   nElem = size;

   return ;
}

/***************************************************************
* dsARRAY::Resize ()
*
***************************************************************/
template <class T> __INLINE void dsARRAY<T>::Resize(int size, const T &val)
{
   STRONG_ASSERT1(size >= 0, size);

   if (size < nElem) {
      for (int i = size; i < nElem; i++) {
         (pData + i)->~T();
      }
      Realloc(size);
   } else if (size > nElem) {
      if (&val >= Begin() && &val < End()) {
         T v = val;
         Realloc(size);
         for (int i = nElem; i < size; i++) {
            New(pData + i, v);
         }
      } else {
         Realloc(size);
         for (int i = nElem; i < size; i++) {
            New(pData + i, val);
         }
      }
   }
   nElem = size;

   return ;
}

/***************************************************************
* dsARRAY::operator [] ()
*
***************************************************************/
template <class T> __INLINE const T& dsARRAY<T>::operator [](int idx) const
{
   STRONG_ASSERT2(idx >= 0 && idx < nElem, idx, nElem);
   return pData[idx];
}

/***************************************************************
* dsARRAY::operator [] ()
*
***************************************************************/
template <class T> __INLINE T& dsARRAY<T>::operator [](int idx)
{
   STRONG_ASSERT2(idx >= 0 && idx < nElem, idx, nElem);
   return pData[idx];
}


/***************************************************************
* dsVECTOR::MergeSortedUnique ()
*    merge two sorted arrays in one (this array) without duplicates
*    arr1 and arr2 MUST BE SORTED and without duplicates!!!!
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP>
void dsVECTOR<T,ALIGNMENT>::MergeSortedUnique (const dsVECTOR<T,ALIGNMENT> &arr1, const dsVECTOR<T,ALIGNMENT> &arr2, const CMP &cmp)
{
   Clear();

   const T *First1 = arr1.Begin();
   const T *First2 = arr2.Begin();

   const T *Last1 = arr1.End();
   const T *Last2 = arr2.End();

   while (First1 < Last1 && First2 < Last2) {
      int rc = cmp.cmp(*First1, *First2);
      if (rc == -1) {
         PushBack(*First1);
         First1++;
      } else if (rc == 1) {
         PushBack(*First2);
         First2++;
      } else {
         PushBack(*First2);
         First2++;
         First1++;
      }
   }
   while (First1 < Last1) {
      PushBack(*First1);
      First1++;
   }
   while (First2 < Last2) {
      PushBack(*First2);
      First2++;
   }
}

/***************************************************************
* dsVECTOR::MergeSorted ()
*    merge two sorted arrays in one (this array)
*    arr1 and arr2 MUST BE SORTED !!!!
***************************************************************/
template <class T, UINT ALIGNMENT>  
template <class CMP>
void dsVECTOR<T,ALIGNMENT>::MergeSorted (const dsVECTOR<T,ALIGNMENT> &arr1, const dsVECTOR<T,ALIGNMENT> &arr2, const CMP &cmp)
{
   Clear();
   Reserve(arr1.Length() + arr2.Length());

   int idx1 = 0, idx2 = 0;
   while (idx1 < arr1.Length() && idx2 < arr2.Length()) {
      int rc = cmp.cmp(arr1[idx1], arr2[idx2]);
      if (rc == -1) {
         PushBack(arr1[idx1++]);
      } else {
         PushBack(arr2[idx2++]);
      }
   }
   while (idx1 < arr1.Length()) {
      PushBack(arr1[idx1++]);
   }
   while (idx2 < arr2.Length()) {
      PushBack(arr2[idx2++]);
   }
}
